{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 图的遍历\n",
    "\n",
    "### 挑战：寻找循环\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 图5-3的循环图邻接列表\n",
    "graph = {\n",
    "    'A':['J'],\n",
    "    'B':['A','F'],\n",
    "    'C':['B'],\n",
    "    'F':['c'],\n",
    "    'J':[]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 等价代码\n",
    "class Graph(): \n",
    "    \"\"\"图类\"\"\"\n",
    "    def __init__(self): \n",
    "        self.graph = {}  # 初始化图的邻接列表\n",
    "    def add_edge(self,u,v): \n",
    "        if v:\n",
    "            point = self.graph.get(u) # 尝试获取结点u\n",
    "            if point:\n",
    "                point.append(v)       # 若存在直接添加u-v的边  \n",
    "            else:\n",
    "                self.graph[u] = [v]   # 若不存在，则先初始化u结点，然后再添加u-v的边\n",
    "        else:\n",
    "            self.graph[u] = list()    # 如果v没有值，添加一个空列表 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict # 引入defaultdict,增加字典的自定义\n",
    "class Graph(): \n",
    "    \"\"\"图类\"\"\"\n",
    "    def __init__(self): \n",
    "        self.graph = defaultdict(list) #  初始化图的邻接列表，自定义字典，默认值是列表\n",
    "    \n",
    "    def add_edge(self,u,v):\n",
    "        if v:\n",
    "            self.graph[u].append(v) # 在u的关键字列表上添加连上v的边\n",
    "        else:\n",
    "            self.graph[u] = list()  # 如果v没有值，添加一个空列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphCycle(Graph):\n",
    "    \"\"\"继承Graph,这是为了检验是否包含循环\"\"\"\n",
    "    def is_cyclic_tool(self, v, visited, recur_stack): \n",
    "        visited[v] = True       # 当前结点已访问\n",
    "        recur_stack[v] = True  # 当前结点放进递归栈中\n",
    "        # 深度优先遍历每一个邻居结点，如果发现邻居是已经访问， \n",
    "        for neighbour in self.graph[v]:\n",
    "            if visited[neighbour] == False: # 如果结点没有访问，进入该结点\n",
    "                if self.is_cyclic_tool(neighbour, visited, recur_stack) == True: \n",
    "                    return True  # 该结点上发现循环\n",
    "            elif recur_stack[neighbour] == True: \n",
    "                return True      # 该结点已访问，并且也在递归栈中，说明找到循环\n",
    "        recur_stack[v] = False # 该结点深度遍历完成，移出递归栈\n",
    "        return False\n",
    "\n",
    "    def is_cyclic(self):\n",
    "        # 如果有循环，回复True,否则回复False\n",
    "        visited = {}   # 初始化参数是否已经访问\n",
    "        recur_stack = {} # 初始化参数是否在递归栈中\n",
    "        for key in self.graph.keys():\n",
    "            visited[key] = False     # 值为未访问状态\n",
    "            recur_stack[key] = False  # 不在递归栈中\n",
    "        for node in self.graph.keys(): # 遍历所有结点 \n",
    "            if visited[node] == False: # 如果结点没有访问，进入该结点\n",
    "                if self.is_cyclic_tool(node, visited, recur_stack) == True: \n",
    "                    return True        # 如果发现有循环，则可以马上返回True\n",
    "        return False  # 遍历结束后，没有找到循环，则返回False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphCycle() \n",
    "g.add_edge('A', 'J') \n",
    "g.add_edge('B', 'A') \n",
    "g.add_edge('B', 'F') \n",
    "g.add_edge('C', 'B') \n",
    "g.add_edge('F', 'C')\n",
    "g.add_edge('J', None)\n",
    "print(g.graph)\n",
    "g.is_cyclic()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 反例-不存在循环\n",
    "g = GraphCycle() \n",
    "g.add_edge('A', 'J') \n",
    "g.add_edge('B', 'A') \n",
    "g.add_edge('B', 'F') \n",
    "g.add_edge('B', 'C') \n",
    "g.add_edge('C', 'F')\n",
    "g.add_edge('F', None)\n",
    "g.add_edge('J', None)\n",
    "print(g.graph)\n",
    "g.is_cyclic()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最小生成树\n",
    "\n",
    "### 克鲁斯卡尔算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphPower(): \n",
    "    \"\"\"有权图类\"\"\"\n",
    "    def __init__(self, points):\n",
    "        self.amount = len(points) # 记录结点的总数\n",
    "        self.points = points      # 记录结点位置和值的关系\n",
    "        self.graph = []           #  初始化图的邻接列表\n",
    "    def add_edge(self, u, v, w):\n",
    "        if u in self.points and v in self.points:\n",
    "            index_u = self.points.index(u)\n",
    "            index_v = self.points.index(v)\n",
    "            self.graph.append([index_u, index_v, w]) # 录入数据\n",
    "        else:\n",
    "            print(\"录入数据有误\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphKruskal(GraphPower): \n",
    "    \"\"\"克鲁斯卡尔算法,输入的是有权无向图，求解最小生成树\"\"\"\n",
    "    def find(self, parent, i):\n",
    "        # 寻找其父结点\n",
    "        if parent[i] == i: \n",
    "            return i \n",
    "        return self.find(parent, parent[i]) \n",
    "   \n",
    "    def kruskalMST(self):\n",
    "        # 基于不相交集实现克鲁斯卡尔算法主程序\n",
    "        # 第一步初始化\n",
    "        MST =[] # 初始化MST，也是最终结果 \n",
    "        parent = [] # 初始化两个列表，用于检测是否有循环,记录结点的父结点\n",
    "        for node in range(self.amount): # 每一个结点创建一个子集合 \n",
    "            parent.append(node) \n",
    "        index_sorted_edge = 0 # 根据权重已排序的边的下标 \n",
    "        index_reslut = 0 # MST列表中的下标 \n",
    "        # 第二步，根据权重排序\n",
    "        self.graph = sorted(self.graph,key=lambda item: item[2]) # 权重w在item中的三个位置\n",
    "        while len(MST) < self.amount -1 : # 结束条件：直到生成树中有（N-1）个边 \n",
    "            # 第三步，选择最小权重的边\n",
    "            u,v,w = self.graph[index_sorted_edge] \n",
    "            index_sorted_edge = index_sorted_edge + 1\n",
    "            # 检查它是否与MST形成一个循环图。如果没有形成循环图，则把该边放进MST，否则将其丢弃\n",
    "            parent1 = self.find(parent, u) \n",
    "            parent2 = self.find(parent ,v)\n",
    "            if parent1 != parent2:\n",
    "                MST.append([u,v,w])         # 结果中添加新的边\n",
    "                parent[parent2] = parent1  # 更新不相交集\n",
    "        self.print_result(MST)\n",
    "\n",
    "    def print_result(self, result):\n",
    "        print(\"输出最小生成树结果\")\n",
    "        total = 0\n",
    "        for u,v,weight in result:\n",
    "            total += weight\n",
    "            print (\"{} -- {} == {}\".format(self.points[u], self.points[v],weight))\n",
    "        else:\n",
    "            print(\"权重总和为：%d\" % total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphKruskal([\"广州\",\"厦门\",\"成都\",\"武汉\",\"上海\",\"北京\"]) \n",
    "g.add_edge(\"广州\",\"厦门\", 2)\n",
    "g.add_edge(\"广州\",\"武汉\", 3) \n",
    "g.add_edge(\"广州\",\"成都\", 2) \n",
    "g.add_edge(\"武汉\",\"厦门\", 4) \n",
    "g.add_edge(\"武汉\",\"成都\", 8) \n",
    "g.add_edge(\"武汉\",\"上海\", 1) \n",
    "g.add_edge(\"武汉\",\"北京\", 9)\n",
    "g.add_edge(\"厦门\",\"上海\", 5)\n",
    "g.add_edge(\"成都\",\"北京\", 7)\n",
    "g.add_edge(\"上海\",\"北京\", 6)\n",
    "g.kruskalMST()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 普里姆算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphArray(): \n",
    "    \"\"\"用邻接矩阵表示图\"\"\"\n",
    "    def __init__(self, points):\n",
    "        self.amount = len(points) # 记录结点的总数\n",
    "        self.points = points      # 记录结点位置和值的关系\n",
    "        # 初始化图的邻接矩阵\n",
    "        self.graph = [[0 for _ in range(self.amount)] \n",
    "                    for _ in range(self.amount)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphPrimMST(GraphArray): \n",
    "    \"\"\"普里姆算法法,输入的是有权无向图，求解最小生成树\"\"\"\n",
    "    def printMST(self, result): \n",
    "        print(\"边 \\t\\t 权重\")  # 结果输出\n",
    "        total = 0\n",
    "        for i in range(1, self.amount):\n",
    "            total +=  self.graph[i][ result[i]]\n",
    "            print(self.points[result[i]], \"-\", self.points[i], \"\\t\", self.graph[i][ result[i]])\n",
    "        print(\"总权重和：\", total)\n",
    "\n",
    "    def min_key(self, key, mst):\n",
    "        # 寻找最小键值的结点下标\n",
    "        min = float(\"Inf\")  # 默认是无穷大\n",
    "        for v in range(self.amount): \n",
    "            if key[v] < min and mst[v] == False: \n",
    "                min = key[v] \n",
    "                min_index = v \n",
    "        return min_index \n",
    "\n",
    "    def primMST(self):\n",
    "        # 普里姆算法主程序\n",
    "        key = [float(\"Inf\")] * self.amount # 默认结点键值是无穷大\n",
    "        parent = [None] * self.amount # 记录最小生成树集合的边，也就是答案\n",
    "        key[0] = 0  # 把第一个结点作为第一个选择的结点，键值设置为0 \n",
    "        MST = [False] * self.amount  # 记录最小生成树集合已访问结点\n",
    "        parent[0] = -1 # 根节点没有父结点，初始化为-1\n",
    "        for _ in range(self.amount):\n",
    "            u = self.min_key(key, MST)  # 选择一个在MST中不存在且具有最小键值的结点u\n",
    "            MST[u] = True # 记录为已访问结点\n",
    "            for v in range(self.amount):\n",
    "                # 当边的权重为正，而且没有被访问，若键值比原来小，则更新结点的键值\n",
    "                if self.graph[u][v] > 0 and MST[v] == False and key[v] > self.graph[u][v]: \n",
    "                    key[v] = self.graph[u][v]  # 更新结点键值\n",
    "                    parent[v] = u  # 更新所选择的边\n",
    "        self.printMST(parent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphPrimMST([\"广州\",\"厦门\",\"成都\",\"武汉\",\"上海\",\"北京\"]) \n",
    "g.graph = [ [0, 2, 2, 3, 0, 0], \n",
    "            [2, 0, 0, 4, 5, 0],\n",
    "            [2, 0, 0, 8, 0, 7],\n",
    "            [3, 4, 8, 0, 1, 9],\n",
    "            [0, 5, 0, 1, 0, 6],\n",
    "            [0, 0, 7, 9, 6, 0]]\n",
    "g.primMST()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 拓扑排序\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphTopological(Graph):\n",
    "    \"\"\"解决拓扑排序问题\"\"\"\n",
    "    def topological_sort_util(self, v, visited, stack): \n",
    "        visited[v] = True       # 该结点变为已访问\n",
    "        for i in self.graph[v]: \n",
    "            if visited[i] == False: # 结点未访问递归调用函数\n",
    "                self.topological_sort_util(i, visited, stack) \n",
    "        # 相邻结点都访问结束后，把该结点放到栈中\n",
    "        stack.insert(0,v)  # 把新入栈元素放在表头\n",
    "\n",
    "    def topological_sort(self):\n",
    "        # 拓扑排序主程序\n",
    "        visited = {}   # 初始化参数是否已经访问\n",
    "        stack = [] # 初始化参数，用列表表示临时栈为空\n",
    "        for key in self.graph.keys():\n",
    "            visited[key] = False     # 值为未访问状态\n",
    "        for node in self.graph.keys(): # 遍历所有结点 \n",
    "            if visited[node] == False: # 结点是否已经访问\n",
    "                self.topological_sort_util(node, visited, stack) # 递归进入结点\n",
    "        print(stack) #把栈保存结果输出"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphTopological() \n",
    "g.add_edge(0, 1) \n",
    "g.add_edge(0, 2) \n",
    "g.add_edge(0, 3) \n",
    "g.add_edge(1, 4) \n",
    "g.add_edge(2, 5) \n",
    "g.add_edge(3, 6)\n",
    "g.add_edge(4, 7)\n",
    "g.add_edge(5, 9)\n",
    "g.add_edge(6, 7)\n",
    "g.add_edge(7, 8)\n",
    "g.add_edge(8, None)\n",
    "g.add_edge(9, 8)\n",
    "g.topological_sort() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = TopologicalGraph() \n",
    "g.add_edge(0, 2) \n",
    "g.add_edge(0, 3)\n",
    "g.add_edge(0, 1) \n",
    "g.add_edge(1, 4) \n",
    "g.add_edge(2, 5) \n",
    "g.add_edge(3, 6)\n",
    "g.add_edge(4, 7)\n",
    "g.add_edge(5, 9)\n",
    "g.add_edge(6, 7)\n",
    "g.add_edge(7, 8)\n",
    "g.add_edge(8, None)\n",
    "g.add_edge(9, 8)\n",
    "g.topological_sort() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 戴克斯特拉算法（Dijkstra’s algorithm）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys  # 引入系统参数，获取系统支撑的最大值\n",
    "class GraphDijkstra(GraphArray):\n",
    "    \"\"\"这是寻找单源结点到其余结点的最短路径\"\"\"\n",
    "    def print_result(self, dist): \n",
    "        print(\"结点 \\t距离源结点的距离\")\n",
    "        for v in range(self.amount): \n",
    "            print(self.points[v], \"\\t\", dist[v])\n",
    "\n",
    "    def min_distance(self, dist, short_path_set):\n",
    "        # 寻找结点到源结点最短距离\n",
    "        min_dist = sys.maxsize #初始化最小距离为系统最大值\n",
    "        for v in range(self.amount):\n",
    "            # 寻找最小距离的结点，并且不在最短路径树集合中\n",
    "            if dist[v] <= min_dist and v not in short_path_set: \n",
    "                min_dist = dist[v] \n",
    "                min_index = v \n",
    "        return min_index \n",
    "\n",
    "    def dijkstra(self, source):\n",
    "        # dijkstra算法主程序，遍历所有结点，放进short_path_set集合中，求得所有结点到源结点的最小距离\n",
    "        distance = [sys.maxsize] * self.amount \n",
    "        distance[source] = 0\n",
    "        short_path_set = set() # 初始化集合为空\n",
    "        for _ in range(self.amount):\n",
    "            # 寻找最小距离的结点，并且不包含在最短路径树集合中\n",
    "            # 而且源结点总是作为第一个结点进入集合\n",
    "            u = self.min_distance(distance, short_path_set)\n",
    "            short_path_set.add(u) # 把结点添加到集合中\n",
    "            # 重新遍历邻接结点，更新结点间最小距离的值\n",
    "            for v in range(self.amount): \n",
    "                if self.graph[u][v] > 0 and v not in short_path_set and distance[v] > distance[u] + self.graph[u][v]: \n",
    "                        distance[v] = distance[u] + self.graph[u][v] #符合条件，更新最短路径值\n",
    "        self.print_result(distance) # 输出结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Driver program \n",
    "g = GraphDijkstra(['A','B','C','D','E','F','H','M','J']) \n",
    "g.graph = [[0, 0, 0, 4, 6, 0, 0, 0, 0], \n",
    "        [0, 0, 9, 8, 0, 0, 1, 7, 0], \n",
    "        [0, 9, 0, 0, 0, 2, 0, 11, 10], \n",
    "        [4, 8, 0, 0, 0, 0, 13, 0, 0],\n",
    "        [6, 0, 0, 0, 0, 4, 0, 0, 0], \n",
    "        [0, 0, 2, 0, 4, 0, 5, 0, 0], \n",
    "        [0, 1, 0, 13, 0, 5, 0, 0, 0], \n",
    "        [0, 7, 11, 0, 0, 0, 0, 0, 3], \n",
    "        [0, 0, 10, 0, 0, 0, 0, 3, 0] \n",
    "        ]; \n",
    "g.dijkstra(0) # A作为源结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Driver program \n",
    "g = DijkstraGraph(['A','B','C','D']) \n",
    "g.graph = [[0, 1, 2, 10], \n",
    "        [1, 0, 1, -20], \n",
    "        [2, 1, 0, 0], \n",
    "        [10, -20, 0, 0],\n",
    "        ]; \n",
    "g.dijkstra(0)# A作为源结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 贝尔曼-福特（Bellman–Ford）算法 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphBellmanFord(GraphPower):\n",
    "    \"\"\"贝尔曼-福特（Bellman–Ford）算法\"\"\"\n",
    "    def print_result(self, dist): \n",
    "        print(\"结点到源结点的距离：\") \n",
    "        for i in range(self.amount): \n",
    "            print(\"{} \\t {}\".format(self.points[i], dist[i])) \n",
    "    \n",
    "    def bellman_ford(self, source):\n",
    "        \"\"\"主程序贝尔曼福特算法求每个结点到源结点最短路径，并且检查是否有负循环\"\"\"\n",
    "        # 第一步：初始化参数，所有结点到源结点的距离为正无穷大 \n",
    "        distance= [float(\"Inf\")]*self.amount # float(\"Inf\")为正无穷大\n",
    "        distance[source] = 0  # 源结点本身距离为0\n",
    "        # 第二步: 进行N-1次的边松弛，找结点到源结点的最短距离\n",
    "        for i in range(self.amount - 1):\n",
    "            for u, v, w in self.graph:\n",
    "                # distance(a) +weight(ab)) < distance(b) 说明存在有更短路径从a到b。\n",
    "                if distance[u] != float(\"Inf\") and distance[u] + w < distance[v]: \n",
    "                        distance[v] = distance[u] + w # 更新最短路径\n",
    "        # 第三步: 检查是否存在负循环,在完成这么N-1次松弛后如果还是可以松弛（找到更短路径）的话说明存在负循环\n",
    "        for u, v, w in self.graph:\n",
    "            if distance[u] != float(\"Inf\") and distance[u] + w < distance[v]: \n",
    "                    print(\"图包含负循环\")\n",
    "                    return\n",
    "        self.print_result(distance) # 打印结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphBellmanFord(['A','B','C','D','E']) # 初始化图，记录结点值\n",
    "g.add_edge('A','B', -1) # 添加边\n",
    "g.add_edge('A','D', 3) \n",
    "g.add_edge('B','D', 2)\n",
    "g.add_edge('B','C', 4)\n",
    "g.add_edge('B','E', 4)\n",
    "g.add_edge('C','E', -2)\n",
    "g.add_edge('E','B', 1)\n",
    "g.add_edge('E','D', 5)\n",
    "g.bellman_ford(0) # 按结点A为源结点计算结点的最短距离\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = BellmanFordGraph(['A','B','C','D','E']) # 初始化图，记录结点值\n",
    "g.add_edge('A','B', -1) # 添加边\n",
    "g.add_edge('A','D', 3) \n",
    "g.add_edge('B','D', 2)\n",
    "g.add_edge('B','C', 4)\n",
    "g.add_edge('B','E', 4)\n",
    "g.add_edge('C','E', -8)\n",
    "g.add_edge('E','B', 1)\n",
    "g.add_edge('E','D', 5)\n",
    "g.bellman_ford(0) # 按结点A为源结点计算结点的最短距离\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最大流问题\n",
    "\n",
    "### 福德-富克逊（Ford-Fulkerson）算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphFordFulkerson(GraphArray): \n",
    "    def BFS(self, s, t, parent):\n",
    "        \"\"\"广度优先搜索\"\"\"\n",
    "        visited =[False]*(self.amount) # 初始化所有结点都没有访问过\n",
    "        queue=[] # 用队列结构来记录访问历史\n",
    "        queue.append(s) # 首先访问起点s\n",
    "        visited[s] = True\n",
    "        while len(queue) > 0:   # 当队列为空，说明全部顶点已经遍历完成 \n",
    "            current_point = queue.pop(0)  # 获取访问历史的队头为当前顶点\n",
    "            for ind, val in enumerate(self.graph[current_point]):\n",
    "                # 逐一访问当前顶点的所有关联点\n",
    "                if visited[ind] == False and val > 0:\n",
    "                    queue.append(ind) # 如果没有访问添加到已访问队列中 \n",
    "                    visited[ind] = True  # 标记结点为已访问\n",
    "                    parent[ind] = current_point   # 记录遍历的路径链接\n",
    "        return True if visited[t] else False  # 如果有路径能到终点t则返回True\n",
    "            \n",
    "    def FordFulkerson(self, source, sink): \n",
    "        # 福德-富克逊算法，计算从起点到终点的最大流问题 \n",
    "        parent = [-1]*(self.amount) # 这个列表记录路径链接\n",
    "        max_flow = 0 # 初始化最大总流量为0 \n",
    "        while self.BFS(source, sink, parent):  # 通过BFS来寻找增广路径\n",
    "            path_flow = float(\"Inf\") # 路径上的流量，初始化为无穷大\n",
    "            s = sink \n",
    "            while(s != source):\n",
    "                # 寻找此增广路径上的最小流量 \n",
    "                path_flow = min(path_flow, self.graph[parent[s]][s]) \n",
    "                s = parent[s]\n",
    "            max_flow += path_flow # 把此增广路径上的流量加到总流量上\n",
    "            # 更新此增广路径上的残余容量\n",
    "            v = sink \n",
    "            while(v != source): \n",
    "                u = parent[v]\n",
    "                self.graph[u][v] -= path_flow  # 正向边减去路径流量\n",
    "                self.graph[v][u] += path_flow  # 反向边加上路径流量\n",
    "                v = parent[v]\n",
    "        print(\"总的最大流量为：\",max_flow)\n",
    "        return max_flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphFordFulkerson(['s','1','2','3','t']) \n",
    "g.graph = [[0, 4, 0, 7, 0], \n",
    "        [0, 0, 3, 2, 0], \n",
    "        [0, 0, 0, 0, 5], \n",
    "        [0, 0, 0, 0, 4], \n",
    "        [0, 0, 0, 0, 0]] \n",
    "source = 0 # 起点下标\n",
    "sink = 4 # 终点下标\n",
    "g.FordFulkerson(source, sink)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 挑战：朋友圈扩列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphFriend(): \n",
    "    def __init__(self, points):\n",
    "        self.amount = len(points) # 记录结点的总数\n",
    "        self.points = points      # 记录结点位置和值的关系\n",
    "        self.group = [[] for i in range(self.amount)] # 无向图，保存所有人的人脉关系\n",
    "        self.groups = [] # 记录全部朋友圈子的情况\n",
    "    \n",
    "    def add_relation(self, u, v):\n",
    "        # 添加朋友关系\n",
    "        if u in self.points and v in self.points:\n",
    "            index_u = self.points.index(u)\n",
    "            index_v = self.points.index(v)\n",
    "            self.group[index_u].append(index_v) # 无向图，两边互加\n",
    "            self.group[index_v].append(index_u) # 无向图，两边互加\n",
    "        else:\n",
    "            print(\"录入数据有误\")\n",
    "\n",
    "    def _count_util(self, v, visited):\n",
    "        # 深度优先搜索发现朋友圈子，参考循环图小节程序\n",
    "        visited[v] = True # 记录结点已经访问\n",
    "        i = 0\n",
    "        while i != len(self.group[v]): # 遍历所有的边\n",
    "            if (not visited[self.group[v][i]]): # 把所有能访问的结点都访问\n",
    "                self._count_util(self.group[v][i], visited) \n",
    "            i += 1\n",
    "        return\n",
    "    \n",
    "    def count_groups(self):\n",
    "        # 统计朋友圈子主程序\n",
    "        visited = [0] * self.amount # 初始化所有结点未被访问\n",
    "        has_group = [] # 保存已经归类的人\n",
    "        for i in range(self.amount):\n",
    "            if (visited[i] == False): # 如果一个结点没有被访问过，就开始一个朋友圈子\n",
    "                self._count_util(i, visited)\n",
    "                g = [] # 记录当前圈子的所有人\n",
    "                for vi,val in enumerate(visited):\n",
    "                    if val: # 如果是True,说明结点已经访问了\n",
    "                        if vi in has_group: # 如果此人已经归类了，跳过不处理\n",
    "                            continue\n",
    "                        else:\n",
    "                            g.append(vi) # 添加此人都这个圈子\n",
    "                            has_group.append(vi) # 保存为已归类的人\n",
    "                self.groups.append(g) # 保存圈子结果\n",
    "        # 输出结果\n",
    "        print(\"存在有%d个朋友圈子\" % len(self.groups))\n",
    "        print(\"每个圈子情况：\")\n",
    "        for i, group in enumerate(self.groups):\n",
    "            print(\"第%d圈子:\" % (i+1), \"-\".join([self.points[p] for p in group]))\n",
    "        \n",
    "    \n",
    "    def _count_degree(self, person, person2, visited):\n",
    "        visited[person2] = True # 记录结点已经访问\n",
    "        # 深度优先探测人脉度\n",
    "        if person in self.group[person2]: # 如果在好友中，那么返回人脉度\n",
    "            return [[person2]]\n",
    "        result = [] # 保存所有人脉路径\n",
    "        for p in self.group[person2]:\n",
    "            if not visited[p]:\n",
    "                for path in self._count_degree(person, p, visited):\n",
    "                    result.append([person2] + path)\n",
    "        return result\n",
    "    \n",
    "    def relation_degree(self, person1, person2):\n",
    "        # 求出两人之间的人脉度，如果互相为好友，则为1，多间隔一个朋友人脉度则多加1\n",
    "        visited = [0] * self.amount # 初始化所有结点未被访问\n",
    "        if person1 not in self.points or person2 not in self.points:\n",
    "            print(\"数据输入有误\")  # 查看输入的结点是否存在，若不存在结束程序\n",
    "            return\n",
    "        p1_index = self.points.index(person1)\n",
    "        p2_index = self.points.index(person2)\n",
    "        if p1_index == p2_index:  # 若是相同的一个人，也不参与运算，马上结束程序\n",
    "            print(\"这是同一个人，请输入不同的两个人\")\n",
    "            return\n",
    "        for group in self.groups:\n",
    "            # 先查看两人是否在一个圈子里面\n",
    "            if p1_index in group and p2_index in group: # 在同一个圈子才有人脉路径\n",
    "                visited[p1_index] = True # 不需要寻找自己本身\n",
    "                visited[p2_index] = True # 不需要寻找自己本身\n",
    "                for path in self._count_degree(p1_index, p2_index, visited):\n",
    "                    path.append(p1_index) # 补充开始结点到结果中\n",
    "                    links = path[::-1] # 翻转列表，让结果更容易理解\n",
    "                    print(\"{}和{}的人脉为{}度\".format(person1, person2, len(links)))\n",
    "                    print(\"-\".join([self.points[p] for p in links]))\n",
    "                break\n",
    "        else:\n",
    "            print(\"{}和{}两人不在一个朋友圈子\".format(person1, person2))            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphFriend(['A','B','C','D','E','F','G']) #  初始化图\n",
    "g.add_relation('A', 'B') # 'A'和‘B’是朋友\n",
    "g.add_relation('A', 'E') # 'A'和‘E’是朋友\n",
    "g.add_relation('B', 'C')\n",
    "g.add_relation('B', 'D')\n",
    "g.add_relation('C', 'E')\n",
    "g.add_relation('F', 'G')\n",
    "g.count_groups() # 这群用户中有多少个群呢？\n",
    "print('---------人脉探索---------------')\n",
    "g.relation_degree('A', 'C')\n",
    "print('---------E-D人脉探索------------')\n",
    "g.relation_degree('E', 'D')\n",
    "print('---------G-E人脉探索------------')\n",
    "g.relation_degree('G', 'E')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class GraphDegree(GraphFriend):\n",
    "    # 继承上面的类，添加计算最长人脉度的函数\n",
    "    def DFS(self, src_person, prev_degree, max_len, visited): \n",
    "        visited[src_person] = 1 # 标记为已访问\n",
    "        curr_degree = 0  # 记录当前人脉度大小\n",
    "        friend = None    # 好友,也就是邻接的结点\n",
    "        for p in self.group[src_person]:# 遍历所有好友\n",
    "            if not visited[p]: # 好友未被访问\n",
    "                curr_degree = prev_degree + 1\n",
    "                # 深度优先搜索探索人脉度\n",
    "                self.DFS(p, curr_degree, max_len, visited)\n",
    "            # 对比，保存当前最长的人脉度\n",
    "            if (max_len[0] < curr_degree): \n",
    "                max_len[0] = curr_degree \n",
    "            curr_degree = 0 # 重新初始化人脉度\n",
    "\n",
    "    def longest_degree(self):\n",
    "        # 求解最长人脉度主程序\n",
    "        max_len = [-999999999999] # 初始化结果\n",
    "        for i in range(0, self.amount):\n",
    "            visited = [False] * (self.amount) # 初始化所有好友未被访问 \n",
    "            self.DFS(i, 0, max_len, visited) # 探索人脉路径\n",
    "        return max_len[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = GraphDegree(['A','B','C','D','E','F','G']) #  初始化图\n",
    "g.add_relation('A', 'B') # 'A'和‘B’是朋友\n",
    "g.add_relation('A', 'E') # 'A'和‘E’是朋友\n",
    "g.add_relation('B', 'C')\n",
    "g.add_relation('B', 'D')\n",
    "g.add_relation('C', 'E')\n",
    "g.add_relation('F', 'G')\n",
    "print(g.longest_degree())\n",
    "g.count_groups() # 这群用户中有多少个群呢？\n",
    "g.relation_degree('E', 'D')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
